package com.leetcode.partition6;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author `RKC`
 * @date 2021/9/21 21:18
 */
public class LC547省份数量 {

    public static int findCircleNum(int[][] isConnected) {
        return unionFind(isConnected);
    }

    public static void main(String[] args) {
//        int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
//        int[][] isConnected = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        int[][] isConnected = {{1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 1, 1}, {1, 0, 1, 1}};
        System.out.println(findCircleNum(isConnected));
    }

    private static int unionFind(int[][] isConnected) {
        int[] root = new int[isConnected.length];
        for (int i = 0; i < root.length; i++) root[i] = i;          //并查集初始化
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = i + 1; j < isConnected.length; j++) {
                if (isConnected[i][j] == 0) continue;
                union(root, j, i);
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < root.length; i++) {
            set.add(find(root, i));
        }
        System.out.println(Arrays.toString(root));
        System.out.println(set);
        return set.size();
    }

    private static void union(int[] root, int x, int y) {
        int rootX = find(root, x), rootY = find(root, y);
        if (rootX != rootY) root[rootX] = rootY;            //将x节点合并到y节点
    }

    private static int find(int[] root, int x) {
        if (x == root[x]) return root[x];
        return find(root, root[x]);             //递归继续进行查找跟节点
    }
}
